package com.chj.zhongji.class15;

import java.util.ArrayList;
import java.util.List;

public class Code03_InsertInterval {

	public static class Interval {
		int start;
		int end;

		Interval() {
			start = 0;
			end = 0;
		}

		Interval(int s, int e) {
			start = s;
			end = e;
		}
	}

	// items中，区间从小到大出现的，无重复区域
	//
	public static List<Interval> insert(List<Interval> items, Interval newItems) {
		List<Interval> result = new ArrayList<>();
		int i = 0;
		// 左侧不会被影响到的区间，原封不动放入结果序列中
		while (i < items.size() && items.get(i).end < newItems.start) {
			result.add(items.get(i++));
		}

		// i 结尾了;要么，items.get(i).end >= newItems.start
		while (i < items.size() && items.get(i).start <= newItems.end) {
			newItems.start = Math.min(newItems.start, items.get(i).start);
			newItems.end = Math.max(newItems.end, items.get(i).end);
			i++;
		}
		result.add(newItems);
		while (i < items.size() && items.get(i).start > newItems.end) {
			result.add(items.get(i++));
		}
		return result;
	}

	public static void main(String[] arg) {
//		{
//			List<Interval> iList = new ArrayList<>();
//			Interval i1 = new Interval(1, 3);
//			Interval i2 = new Interval(6, 9);
//			iList.add(i1);
//			iList.add(i2);
//			Interval newItems = new Interval(2, 5);
//			List<Interval> res1 = insert(iList, newItems);
//			System.out.println(res1);
//		}

		{
			List<Interval> iList = new ArrayList<>();
			Interval i1 = new Interval(1, 2);
			Interval i2 = new Interval(3, 5);
			Interval i3 = new Interval(6, 7);
			Interval i4 = new Interval(8, 10);
			Interval i5 = new Interval(12, 16);
			iList.add(i1);
			iList.add(i2);
			iList.add(i3);
			iList.add(i4);
			iList.add(i5);
			Interval newItems = new Interval(4, 9);
			List<Interval> res1 = insert(iList, newItems);
			System.out.println(res1);
//			[1,2],[3,10],[12,16]
		}
	}

}
